Educational Codeforces Round 177 (Rated for Div. 2) A-D 题解

A - Cloudberry Jam

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T; cin >> T;
    while (T--) {
        int x; cin >> x;
        cout << x * 2 << '\n';
    }
}

B - Large Array and Segments

Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void solve() {
    ll n, k, x; cin >> n >> k >> x;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    ll sum = 0;
    for (int i = 1; i <= n; i++) sum += a[i];
    ll cnt = (x - 1) / sum;
    ll ans = cnt * n;
    x -= cnt * sum;
    for (int i = n; i >= 1; i--) {
        if (x > a[i]) {
            x -= a[i];
            ans += 1;
        }
        else {
            break;
        }
    }
    cout << max(0ll, n * k - ans) << '\n';
    return;
}

int main() {
    // freopen ("B.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T; cin >> T;
    while (T--) solve();
    return 0;
}

C - Disappearing Permutation

Question

给出一个长度为 $n$ 的排列 ${a}$

每次操作给定一个 $x$ ，永久得把 $a_{x}$ 修改成 $0$

每次操作后询问，最多执行几次 $a_{i} = i$ 才能使 $a$ 重新变成一个排列

Solution

把一个 $i$ 看个一个点， $i$ 向 $a_{i}$ 连边，那么这个图会变成几个连通块

如果一个联通块中的一个 $a_{i}$ 变成 $0$ 了，那么整个联通块都需要执行 $a_{i} = i$ 的操作，操作次数就是联通块的大小

用并查集或者其他数据结构都可

Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    vector<int> fa(n + 1), siz(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        fa[i] = i; siz[i] = 1;
    }

    function<int(int)> find = [&](int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    };

    function<void(int, int)> merge = [&](int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return;
        if (siz[fx] < siz[fy]) swap(fx, fy);
        fa[fy] = fx;
        siz[fx] += siz[fy];
        siz[fy] = 0;
    };

    for (int i = 1; i <= n; i++) {
        merge(i, a[i]);
    }

    int ans = 0;
    vector<int> b(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        int fx = find(x);
        if (b[fx] == 0) {
            ans += siz[fx];
            b[fx] = 1;
        }
        cout << ans << ' ';
    }
    cout << '\n';
}

int main() {
    freopen ("C.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

D - Even String

Question

给定一个数组 $c_{i}$ ，询问满足如下条件字符串的方案数：

对于任何 $s_{i} = s_{j}$ ，都需要满足： $| i - j |$ 是一个偶数
字符 $x$ 在 $s$ 中出现的次数为 $c_{x}$
$\sum c_{i} \leq 5 \times 10^{5}$

Solution

先不考虑第一个条件，那么这个就是一个经典的组合数学问题，答案就是

\frac{A_{n}^{n}}{A_{c_{1}}^{c_{1}} \times A_{c_{2}}^{c_{2}} \times \dots \times A_{c_{26}}^{c_{26}}}

再考虑加上第二个条件，一种简单的想法是分奇偶，分出那些字母是在奇数位置的，哪些是在偶数位置的，然后使用上面那个公式算出即可，但是这样的时间复杂度是 $O (2^{26} \times 26)$ 会超时

观察到 $\sum c_{i} \leq 5 \times 10^{5}$ ，考虑能不能像背包问题那样，对于一个字母，考虑放在奇数位置还是偶数位置

所以定义动态规划： $f [i] [o d d_s u m]$ 表示，前 $i$ 个字母，奇数位的和为 $o d d_s u m$ 的方案数

前 $i$ 个字母的数字个数总和为 $p r e_s u m$ ，那么偶数位置的和也可以被唯一确定是 $p r e_s u m - o d d_s u m$ ，就不用定义在状态里面了

考虑转移：

如果放在奇数位置

前一个状态： $f [i - 1] [o d d_s u m - c_{i}] = \frac{A_{o d d_s u m - c_{i}}^{o d d_s u m - c_{i}}}{\prod_{i \in 之前被选中在奇数位} A_{i}}$

观察和当前状态之间的关系，可以得到递推关系

f [i - 1] [o d d_s u m - c_{i}] \times \frac{A_{o d d_s u m}^{o d d_s u m}}{A_{o d d_s u m - c_{i}}^{o d d_s u m - c_{i}} \times A_{c_{i}}^{c_{i}}} = \frac{A_{o d d_s u m - c_{i}}^{o d d_s u m - c_{i}}}{\prod_{i \in 之前被选中在奇数位} A_{i}} \times \frac{A_{o d d_s u m}^{o d d_s u m}}{A_{o d d_s u m - c_{i}}^{o d d_s u m - c_{i}} \times A_{c_{i}}^{c_{i}}} \to f [i] [o d d_s u m]

如果放在偶数位置

也同理：

f [i - 1] [o d d_s u m] \times \frac{A_{e v e n_s u m}^{e v e n_s u m}}{A_{e v e n_s u m - c_{i}}^{e v e n_s u m - c_{i}} \times A_{c_{i}}^{c_{i}}} \to f [i] [o d d_s u m]

其中： $e v e n_s u m = p r e_s u m - o d d_s u m$

考虑答案：

设 $s u m = \sum c_{i}$

如果 $s u m$ 为偶数，答案就是 $f [26] [s u m / 2]$
如果 $s u m$ 为奇数，答案就是 $f [26] [⌊ s u m / 2 ⌋ + 1]$

最后把第一维改成滚动数组就可以通过了

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long

constexpr int MAXN = 5e5 + 5;
using ll = long long;
constexpr ll MOD = 998244353;

ll Fac[MAXN], Inv[MAXN];

ll fast_pow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void init() {
    Fac[0] = 1;
    for (int i = 1; i < MAXN; i++)
        Fac[i] = Fac[i - 1] * i % MOD;
    Inv[MAXN - 1] = fast_pow(Fac[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 0; i--)
        Inv[i] = Inv[i + 1] * (i + 1) % MOD;
}


ll F[2][MAXN];

void solve() {
    vector<int> c(27);
    ll sum = 0;
    for (int i = 1; i <= 26; i++)
        cin >> c[i], sum += c[i];
    
    ll pre_sum = 0; // 前 i 的和
    F[0][0] = 1;
    for (int i = 1; i <= 26; i++) {
        for (int j = 0; j <= sum; j++)
            F[i & 1][j] = 0;

        if (c[i] == 0) {
            for (int j = 0; j <= sum; j++)
                F[i & 1][j] = F[1 - i & 1][j];
            continue;
        }
        pre_sum += c[i];

        for (ll odd_sum = pre_sum; odd_sum >= 0; odd_sum --) {
            ll even_sum = pre_sum - odd_sum;
            if (odd_sum >= c[i]) { // 加到奇数里面
                ll now = F[1 - i & 1][odd_sum - c[i]] * Inv[odd_sum - c[i]] % MOD * Fac[odd_sum] % MOD * Inv[c[i]] % MOD;
                F[i & 1][odd_sum] = (F[i & 1][odd_sum] + now) % MOD;
            }
            if (even_sum >= c[i]) { // 加到偶数里面
                ll now = F[1 - i & 1][odd_sum] * Inv[even_sum - c[i]] % MOD * Fac[even_sum] % MOD * Inv[c[i]] % MOD;
                F[i & 1][odd_sum] = (F[i & 1][odd_sum] + now) % MOD;
            }
        }
    }
    ll ans = 0;
    if (sum % 2 == 0) {
        ans = F[26 & 1][sum / 2];
    }
    else {
        ans = F[26 & 1][sum / 2 + 1];
    }
    cout << ans << '\n';
}

signed main() {
    // freopen ("D.in", "r", stdin);
    init();
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}